/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.math;

import java.util.HashSet;
import java.util.Set;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/9
 */
public class Lesson1_p {

    public static int find(int[] input) {
        int len = input.length;
        int val1, val2;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                val1 = input[i];
                val2 = input[j];
                if (val1 == val2) {
                    return val1;
                }
            }
        }
        throw new RuntimeException("没有找到");
    }

    public static int find1(int[] input) {
        int len = input.length;
        int value;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            value = input[i];
            if (set.contains(value)) {
                return value;
            }
            set.add(value);
        }
        throw new RuntimeException("没有找到");
    }

    //    推到应该是:
//    原始数据: 1,2...m,m,...n (是否有序对此题不重要)
//    所有数字: 1,2,...m,...n
//    因为 x^x = 0
//    令a = 1^2...^m...^n
//            b = 1^2...^m^m...^n
//    则有: a^b = (1^2...^m...^n)^(1^2...^m...^n)^m = 0^m = m
    public static int find2(int[] input) {
        int sum1 = 1, sum2 = 1;
        int len = input.length;
        int max = input[len - 1];
        for (int i = 2; i <= max; i++) {
            sum1 ^= i;
            System.out.println(sum1);
        }
        for (int i = 1; i < len; i++) {
            sum2 ^= input[i];
            System.out.println(sum2);
        }
        return sum1 ^ sum2;
    }

    public static void main(String[] args) {
        System.out.println(find2(new int[]{1, 2, 3, 4, 5, 6, 6, 7, 8}));
    }
}
